modeltheoryfandomcom-20200213-history
Existential closedness
Let M'' ⊆ ''N be an inclusion of structures, in the same signature. One says that M'' is '''existentially closed' in N'' (sometimes denoted ''M ≤1 N'') if for every existential formula \phi(x) and every tuple ''a from M'', one has : M \models \phi(a) \iff N \models \phi(a) The left-to-right direction is automatic, by general properties of existential formulas. So the real content here is that N \models \phi(a) implies M \models \phi(a) . We can also describe existential closedness in terms of quantifier-free formulas: ''M is existentially closed in N'' if and only if for every quantifier-free formula \psi(x;y) , every tuple ''a from M'', and every tuple ''b from N'', if N \models \psi(a;b) , then M \models \psi(a;b') for some tuple ''b' ''from ''M. Equivalently : N \models \exists y : \psi(a;y) \implies M \models \exists y : \psi(a;y) . Since \exists y : \psi(x;y) can be any existential formula, this is equivalent to the definition in terms of existential formulas. Another way of paraphrasing this is: if some quantifier-free M''-definable set has a point in ''N, then it has one in M''. If ''M is a model of a theory T'', we say that ''M is existentially closed if M'' is existentially closed in every model of ''T extending M''. This depends on the theory ''T, and is not a property of the structure M'' alone. To some extent, one can think of "existential closedness" for models as generalizing the notion of "algebraic closedness" for fields. Indeed, if ''T is the theory of fields, the existentially closed models of T'' are exactly the algebraically closed fields (proven below). Checking existential closedness A theory ''T is model complete if and only if all models are existentially closed. Equivalently, whenever M'' ⊆ ''N is an inclusion of models of T'', ''M is existentially closed in N''. There are several other characterizations of model completeness, and it turns out, for example, that any theory with quantifier elimination is model complete. In checking model completeness, it turns out that one can restrict to the case of very simple formulas: '''Lemma:' Let M'' ⊆ ''N be an inclusion of structures. For M'' to be existentially closed in ''N it is sufficient (and obviously necessary) that the following condition holds: * If \phi_1(x;y),\ldots,\phi_n(x;y) is a finite list of atomic and negated-atomic formulas, and a'' is a tuple from ''M, then :: N \models \exists y : \bigwedge_{i = 1}^n \phi_i(a;y) \implies M \models \exists y : \bigwedge_{i = 1}^n \phi_i(a;y) :or equivalently, :: \bigcap_{i = 1}^n \phi_i(a;N) \ne \emptyset \implies \bigcap_{i = 1}^n \phi_i(a;M) . Intuitively speaking, the \phi_i(a;y) are "equations" in the variables y'', with "coefficients" ''a from M''. We are saying that if a system of equations over ''M has a solution in N'', then it has one in ''M. Proof: Existential closedness means that for every existential formula \psi(x) and every tuple a'' from ''M, : N \models \psi(a) \implies M \models \psi(a) \qquad (*) . The Lemma is saying that it suffices to check only the existential formulas of the form \exists y : \phi(x;y) with \phi(x;y) a conjunction of atomic and negated atomic formulas. Why does this suffice? Because of the following three easily-verified facts: * If (*) holds for \psi_1(x) and \psi_2(x) , then it holds for \psi_1(x) \vee \psi_2(x) . * Every quantifier free formula can be written as a disjunction of conjunctions of possibly negated atomic formulas. This follows from the distributive law in boolean algebra. * \exists y : \chi_1(y) \vee \chi_2(y) is logically equivalent to \left(\exists y : \chi_1(y)\right) \vee \left(\exists y : \chi_2(y)\right) . In particular, we can pull disjunctions outside the quantifiers. The second two facts imply that any existential formula is a disjunction of existential formulas of the form mentioned in the Lemma (disjunction-free existential formulas). The first bullet point allows us therefore to reduce to just checking those formulas. QED. Example: Rings Let S'' be a subring of ''R. When is S'' existentially closed in ''R? By the Lemma above, a necessary and sufficient condition is that whenever \phi_i(x;y) is a posibly negated atomic formula for each i'', and ''s is a tuple from S'', we have : R \models \exists y : \bigwedge_{i = 1}^n \phi_i(s;y) \implies S \models \exists y : \bigwedge_{i = 1}^n \phi_i(s;y) . In the language of rings, the \phi_i can only be of the form P(x;y) = 0 or P(x;y) \ne 0 , where P(x;y) is a polynomial in the variables ''x and y'', with \mathbb{Z} -coefficients. In other words, ''S is existentially closed in R'' if and only if the following holds: :: If a system of algebraic equations and inequations, with coefficients in ''S, has a solution in R'', then it has a solution in ''S. Here are some non-examples: * The integers Z''' are not existentially closed in the rationals '''Q. Indeed, the equation 2''x'' = 1 has a solution in Q''', but not in '''Z. * The rationals Q''' are not existentially closed in the reals '''R because the equation x''2 = 2 has a solution in '''R' but not in Q'''. * Similarly, the reals are not existentially closed in '''C, because -1 has a square root in C''' but not in '''R. * The integers Z''' are not existentially closed in '''Z × Z', because the system of equations ''u''2 = ''u, u'' ≠ 0, ''u ≠ 1 has a solution in '''Z × Z''' (namely, the element (1,0)), but does not have a solution in '''Z. * More generally, if S'' ⊆ ''R, S'' is an integral domain, and ''R is not, then S'' is not existentially closed in ''R', because the system ''xy = 0, x'' ≠ 0, ''y ≠ 0 has a solution in R'', but not in ''S. * If S'' is a reduced ring (no nilpotents), and ''R is not, then S'' is not existentially closed in ''R, because the system x''2 = 0, ''x ≠ 0 has a solution in R'', but not in ''S. It is less trivial to produce actual examples: Theorem: Let K'' be algebraically closed, and let ''L be an extension field. Then L'' is existentially closed in ''K. For example, the field of algebraic numbers is existentially closed in the field of complex numbers. Proof: Given a system of equations over K'', with a solution in ''L, we can safely replace all inequations with equations, by replacing : P(x) \ne 0 with : P(x)t = 1 where t'' is a new dummy variable. This can be done safely, because ''L is a field. So we need to show that any system of equations over K'' which has a solution in ''L already has one in K''. Write the system as \bigwedge_{i = 1}^n P_i(\vec{x}) = 0 , where each P_i(\vec{x}) is a polynomial over ''K. If this system has no solution in K'', then by the Nullstellensatz, the polynomials P_i(\vec{x}) generate the unit ideal (1) in the polynomial algebra Kx . That is, there exist polynomials Q_i(\vec{x}) such that : 1 = \sum_i P_i(\vec{x})Q_i(\vec{x}) . This remains true after base changing to ''L, of course, and consequently no point with coordinates in L'' can be a simultaneous zero of all the P_i 's. This contradicts the assumption that the system of equations had some solution in ''L. QED. As an example "application" of this fact, we see that the theory of algebraically closed fields is model complete. Also, Corollary: A field is existentially closed (as a field) if and only if it is algebraically closed. Proof: By the Theorem, every algebraically closed field is existentially closed. Conversely, if K'' is a field that is not algebraically closed, then ''K is not existentially closed in its algebraic closure: some equation in one variable has a solution in the algebraic closure of K'', but not in ''K itself. QED. Existentially closed models of Inductive Theories In general, a theory may have no existentially closed models. For example, let T'' be the theory of ordered sets (''M,<) with the property that every element of M'' has a successor and a predecessor, i.e., : \forall x \exists y : x < y \wedge \neg \exists z : x < z < y : \forall x \exists y : x > y \wedge \neg \exists z : x > z > y Then ''T has models (for example, the integers with the usual order), but T'' has no existentially closed models. For if ''M is any model, and a'' and ''b are two consecutive elements in M'', then we can make an extending model ''N by adding one new element between a'' and ''b. Then the system of equations a'' < ''x < b'' has a solution in ''N but not in M''. It turns out that the key problem with this theory is that it is not inductive. '''Theorem:' Let T'' be an inductive theory. Then every model of ''T can be embedded into an existentially closed model of T''. ''Proof: The rough idea is as follows: given a model M'', if some system of equations over ''M has a solution in an extension of M'', but doesn't have one in ''M, then add a solution. Repeat this enough, and M'' will eventually be existentially closed. This requires transfinite induction, so we need "inductive" to be able to handle the limit ordinals. More formally, let us first prove '''Claim:' If M'' is a model of ''T, then we can make a model N''1 of ''T, extending M'', with the following property: * If \phi(x;a) is a quantifier-free formula over ''M, and N''2 is a model of ''T extending N''1, then :: N_2 \models \exists x : \phi(x;a) \implies N_1 \models \exists x : \phi(x;a) So roughly, any system of equations over ''M which has a solution in an extension of N''1 already has a solution in ''N''1. ''Proof: Let \{\phi_\alpha(x;a_\alpha) : \alpha < \lambda\} be an enumeration of all quantifier-free formulas over M''. Build an ascending sequence of models M_\alpha for \alpha \le \kappa inductively as follows: * If \alpha = 0 , take M_\alpha = M * If \alpha is a limit ordinal, take M_\alpha = \bigcup_{\beta < \alpha} M_\beta . This is a model (of ''T) because T'' is inductive. * Let M_{\alpha+1} be constructed as follows. If there is a model ''N of T'' extending M_{\alpha} such that \phi_\alpha(N;a_\alpha) is non-empty, then take M_{\alpha+1} = N (for some arbitrary choice of ''N). Otherwise, take M_{\alpha+1} = M_{\alpha} . Let N''1 be M_\lambda . Then ''N''1 is a model of ''T extending M''. It has the desired property. Indeed, suppose \phi(x;a) is a quantifier-free formula over ''M, N''2 is a model extending ''N''1, and suppose that : N_2 \models \exists x : \phi(x;a) Because we enumerated all the quantifier-free formulas over ''M, \phi(x;a) is \phi_\alpha(x;a_\alpha) for some \alpha . Now : M_\alpha \subset M_\lambda = N_1 \subset N_2 and \phi_\alpha(N_2;a_\alpha) is non-empty. Therefore, by choice of M_{\alpha+1} , we also have : \emptyset \ne \phi_\alpha(M_{\alpha+1};a_\alpha) \subset \phi_\alpha(N_1;a_\alpha) So : N_1 \models \exists x :\phi(x;a) Thus : N_2 \models \exists x : \phi(x;a) \implies N_1 \models \exists x : \phi(x;a) . QEDclaim. Now given a model M'' of ''T, build an increasing sequence M''1 ⊆ ''M''2 ⊆ ... of models as follows: * ''M''1 = ''M * Mi+1 is obtained by applying the Claim to Mi. In particular, if some existential sentence over Mi holds in an extension of Mi+1, then it holds in Mi+1. Let N'' be the union of this chain. This is still a model, because ''T is inductive. We claim that N'' is existentially closed. Indeed, let ''N''2 be a model extending ''N. Let \phi(x;a) be a quantifier-free formula over N'', satisfiable in ''N''2. The tuple ''a is finite, so must come from some Mi. Then : N_2 \models \exists x : \phi(x;a) \implies M_{i+1} \models \exists x : \phi(x;a) \implies N \models \exists x :\phi(x;a) The first implication follows from the choice of M''i''+1. The second implication follows from general facts about existential formulas (they are preserved upwards in inclusions). So N'' is existentially closed in ''N''2. In conclusion, ''N is an existentially closed model of T'', and it extends the original model ''M. QED.